# encode: utf-8 (It is best to open using vscode)
"""
1. [大整数减法-bilibili视频(点此进入)](https://www.bilibili.com/video/BV1Xb4y1b7HR)
2. [大整数除法-bilibili视频(点此进入)](https://www.bilibili.com/video/BV1BP4y1L7y2)
"""


def sub(s1, s2):
    def f(s1, s2, ac):
        if s2 == "":
            s2 = "0"   # 空串将无法索引，因此我们需要将空串转为"0"进行减法
        if s2 == "0" and ac == 0:
            return s1  # 当s2为0且ac也为0的时候，结束减法

        t = ord(s1[-1]) - ord(s2[-1]) + ac
        if t >= 0:
            return f(s1[:-1], s2[:-1], 0) + str(t)
        else:
            return f(s1[:-1], s2[:-1], -1) + str(t + 10)

    r = f(s1, s2, 0).lstrip("0")
    if r == "":
        r = "0"
    return r


def div(s1, s2):
    def BaseDiv(s3):
        t = 0  # 使用减法模拟除法，用t记录减法次数即商
        while True:
            # 当s3长度比s2长度短，哪s3必然比s2小
            if len(s3) < len(s2):
                break
            # 当s3与s2长度相等但是s3比s2小
            if len(s3) == len(s2) and s3 < s2:
                break
            s3 = sub(s3, s2)
            # 否则做减法运算，运算到不能做减法为止，那么t就是除法的商
            t = t + 1
        return str(t), s3

    def f(s3):
        if len(s3) - len(s2) <= 1:
            return BaseDiv(s3)

        m = len(s2) + 1
        theFirstHalf, theSecondHalf = s1[:m], s1[m:]
        quotient1, remainder1 = f(theFirstHalf)
        quotient2, remainder2 = f(remainder1 + theSecondHalf)

        # 补足第二段的前导0
        while len(quotient2) < len(theSecondHalf):
            quotient2 = "0" + quotient2

        # 去除前导0
        remainder2 = remainder2.lstrip("0")
        if remainder2 == "":
            remainder2 = "0"
        return quotient1 + quotient2, remainder2

    return f(s1)


comment1 = """--------测试sub方法--------"""
print(comment1)
print(sub("111", "11"))
print(sub("10000000000", "23"))
print(sub("10000000000", "128"))
print(sub("10000000000", "233"))
print(sub("10000000000", "100000"))

comment2 = """--------测试divide方法--------"""
print(comment2)
print(div("100", "3"))
print(div("10000000000", "100000"))
print(div("10000000000", "111111"))
print(div("10000000000", "12312313"))

# 算法有待提高，如下列式子，随着递归层数的增加，会超出python最大递归层数
# 同时因为递归层数过多，效率也会极差，
# 但是大数除一个大数这个问题已经解决了
# 大数除小数暂时没有解决
# print(div("10000000000", "11"))
